/*
 * @lc app=leetcode.cn id=98 lang=golang
 *
 * [98] 验证二叉搜索树
 */

// 2.
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	var helper func(root *TreeNode, lower, upper int) bool
	helper = func(root *TreeNode, lower, upper int) bool {
		if root == nil {
			return true
		}
		if root.Val <= lower || root.Val >= upper {
			return false
		}
		return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
	}
	return helper(root, math.MinInt64, math.MaxInt64)
}

// @lc code=end

// 1-2. 中序遍历 升序
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	pre := math.MinInt64
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		if stack[len(stack)-1].Val <= pre {
			return false
		}
		pre = stack[len(stack)-1].Val
		root = stack[len(stack)-1].Right
		stack = stack[:len(stack)-1]
	}

	return true
}

// @lc code=end

// 1-1. 中序遍历 升序
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	flag := true
	pre := math.MinInt64
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		if node.Val <= pre {
			flag = false
			return
		}
		pre = node.Val
		inorder(node.Right)
	}

	inorder(root)
	return flag
}

// @lc code=end

// 这个不行，因为只能证明单个的树是搜索树，不能证明整体的
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	if root != nil {
		if root.Left != nil && root.Left.Val >= root.Val {
			return false
		}
		if root.Right != nil && root.Right.Val <= root.Val {
			return false
		}
		return isValidBST(root.Left) && isValidBST(root.Right)
	}
	return true
}

// @lc code=end
